class Solution {
    public:
        int change(int amount, vector<int>& coins) {
            int n = coins.size();
            vector<vector<int>> dp(n+1,vector<int>(amount+1));
            dp[0][0] = 1;
            int ret = 0;
            for(int i = 1 ; i < n+1 ; i++){
                for(int j = 0 ; j < amount+1 ;j++){
                    dp[i][j] = j>=coins[i-1] ? dp[i-1][j]+dp[i][j-coins[i-1]] : dp[i-1][j];
                }
            }
            return dp[n][amount];
        }
    };